package jianzhioffer;

// 剑指 Offer 12. 矩阵中的路径
public class Exist {

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] used = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0, used, board, word)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(int x, int y, int start, boolean[][] used, char[][] board, String word) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || used[x][y] || board[x][y] != word.charAt(start)) {
            return false;
        }
        if (start == word.length() - 1) {
            return true;
        }
        used[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];
            if (dfs(mx, my, start + 1, used, board, word)) {
                return true;
            }
        }
        // 类似回溯
        used[x][y] = false;
        return false;
    }
}
